\chapter{Methodology}

In this chapter we look at what is the form(pattern) of an RTL expression and how this could be separated from an RTL template. Then we see how MD files were tested for 
similarities. Finally we see, how a pattern can be instantiated with machine-specific parameters to construct a new RTL template.

\section{Extracting the Form of an RTL Expression}


Even though the Register Transfer Expressions in an MD file represents machine instructions for a specific machine, their form is 
machine-independent\cite{Davidson}. This section explains what is the form and how this form can be extracted from an RTL expression.

Let us take for example, a define\_insn expression from mips.md file 

\begin{example}
\onehalfspacing
\begin{verbatim}
(define_insn "add<mode>3"
  [(set (match_operand:ANYF 0 "register_operand" "=f")
	(plus:ANYF (match_operand:ANYF 1 "register_operand" "f")
		   (match_operand:ANYF 2 "register_operand" "f")))]
  ""
  "add.<fmt>\t%0,%1,%2"
  [(set_attr "type" "fadd")
   (set_attr "mode" "<UNITMODE>")])
\end{verbatim}
 
\end{example}


Here the RTL template is 


\begin{verbatim}
 [(set (match_operand:ANYF 0 "register_operand" "=f")
	(plus:ANYF (match_operand:ANYF 1 "register_operand" "f")
		   (match_operand:ANYF 2 "register_operand" "f")))]
\end{verbatim}


This can be represented in a tree form as, 
\begin{figure}[H]
\centering%
\includegraphics[scale = 0.4]{add.pdf}
\caption{Add Template}
\label{fig:FigureAdd}
\end{figure}






The form of the above RTL template can be represented as,

\begin{figure}[H]
\centering%
\includegraphics[scale = 0.4]{add-form1.pdf}
\caption{Add - Form of the template}
\label{fig:FigureAdd-Form}
\end{figure}

The nodes that are labeled arg0, arg1, arg2, etc., can be termed as holes which can be filled by suitable parameters. The mode of the operator plus is 
also not part of the form, because, the modes supported are machine specific. Similarly, the
match\_operand expressions are machine-specific because, they have fields like predicate, constraint and mode. These fields tells how the operand should
be chosen in a machine-specific way. 
We can see that the form depicted in figure
\ref{fig:FigureAdd-Form}, can be used by any machine, as it has no machine-specific parameters. Any machine can use this form after filling in details about
the arguments for the operators set and plus and the mode supported by the operator plus.

\begin{definition}
An RTL template stripped off its machine-specific parameters, containing only the form of the template is called its \emph{RTL pattern} or simply
\emph {pattern}.
\end{definition}

The patterns when filled(instantiated) with suitable machine-specific 
parameters like modes or match\_operand expressions can give the original RTL template.






\begin{table}[htb!]
 \centering
\begin{tabular}{|c | c | c|}
\hline
S.No & Pattern & No. of Occurrence\\
\hline
1 & \includegraphics[scale = 0.5]{G0.pdf} & 17 \\
\hline
2 & \includegraphics[scale = 0.5]{G1.pdf} & 2\\
\hline
3 & \includegraphics[scale = 0.5]{G2.pdf} & 2\\
\hline
4 & \includegraphics[scale = 0.5]{G3.pdf} & 1\\
\hline
\end{tabular}
\caption{Summary of Patterns in Add instructions from mips.md}
\label{tab:addsummary}
\end{table}


A look at the list of MD file instructions of MIPS, that deal exclusively with addition tells that, there are 7 define\_insn instructions, 4 define\_split instructions and one each of define\_expand and
define\_insn\_and\_split instructions. These instructions together have 22 RTL templates. But when we extract the patterns from each of these 22 RTL templates, there are
only 4 unique RTL patterns in total.

We see from table \ref{tab:addsummary}, that pattern1 repeats itself 17 times, with varying machine-specific mode and operand constraints.
Extracting patterns from the addition instructions of the mips machine description was relatively simple. It was enough to 
extract the operators set, plus, zero\_extend, sign\_extend and truncate and excluding the modes and match\_operand and 
match\_dup expressions. But to extract patterns from the whole of machine description files, we need to classify what forms
part of the pattern and what should be ignored.


The RTL expressions in rtl.def are classified into several classes. The classification is based on the type of their operation and their
operands. Below is a list of RTL classes along with a brief description about each of them\cite{gccint}.
\begin{itemize}
 \item RTX\_OBJ: 
    An RTX code that represents an actual object, such as a register (reg) or a memory location (mem, symbol\_ref). 
 \item RTX\_CONST\_OBJ:
    An RTX code that represents a constant object. 
 \item RTX\_COMPARE: 
    An RTX code for a non-symmetric comparison, such as geu and lt.
 \item RTX\_COMM\_COMPARE: 
    An RTX code for a symmetric (commutative) comparison, such as eq, ordered, etc.
 \item RTX\_UNARY: 
    An RTX code for a unary arithmetic operation, such as neg, not, abs, etc. This category also includes value extension 
    (sign or zero) and conversions between integer and floating point.
 \item RTX\_COMM\_ARITH: 
    An RTX code for a commutative binary operation, such as plus, and, ne, eq, etc.
 \item RTX\_BIN\_ARITH: 
    An RTX code for a non-commutative binary operation, such as minus, div, ashiftrt, etc.
 \item RTX\_BITFIELD\_OPS: 
    An RTX code for a bit-field operation. Currently only zero\_extract and sign\_extract are part of it. 
 \item RTX\_TERNARY: 
    An RTX code for other three input operations. Currently only if\_then\_els, vec\_merge, sign\_extract, zero\_extract, and fma are included.
 \item RTX\_INSN: 
    An RTX code for an entire instruction. 
 \item RTX\_MATCH: 
    An RTX code for something that matches in insns, such as match\_dup. These only occur in machine descriptions.
 \item RTX\_AUTOINC: 
    An RTX code for an auto-increment addressing mode, such as post\_inc.
 \item RTX\_EXTRA: 
    All other RTX codes. This category includes the remaining codes used only in machine descriptions (define\_*, etc.). It also
    includes all the codes describing side effects (set, use, clobber, etc.) and the non-insns that may appear on an insn chain,
    such as note, barrier, and code\_label. subreg is also part of this class. 
\end{itemize}


From the above list, the obvious choices for classes of RTL expressions which will be part of the patterns are,

\begin{itemize}
 \item RTX\_COMPARE
 \item RTX\_COM\_COMPARE
 \item RTX\_UNARY
 \item RTX\_COMM\_ARITH
 \item RTX\_BITFIELDS\_OPS
 \item RTX\_TERNARY
 \item RTX\_AUTOINC
\end{itemize}
 
Apart from this, the form of an RTL expression contains a few RTL expressions from the class RTX\_EXTRA. They are called \emph{Side Effect Expressions}. They are so named, 
because they change the state of the machine. Side effect expressions include operators {\tt set}, {\tt return}, {\tt call}, {\tt clobber}, {\tt use}, {\tt parallel}, 
{\tt cond\_exec}, {\tt sequence}, {\tt asm\_input}, {\tt unspec}, {\tt unspec\_volatile}, {\tt addr\_vec} and {\tt addr\_diff\_vec}.

An \emph{internal node} of a tree is that node that has child nodes. We have seen quite a few examples where the RTL expressions and templates where represented as trees. 
The RTL expressions that are part of the pattern are those that appear as internal nodes in the tree form of the RTL expressions. The RTL expressions which are leaves in an
RTL tree form, are constants, registers or memory locations which are chosen in a machine specific way. In summary, the RTL expressions which are part of the pattern, tells
what operation is being done, and this has the same meaning across machines.

So, to extract the pattern from an RTL template, we must traverse the tree form of it and retain all nodes which form part of the pattern and create holes in place of
nodes which are machine specific.

The list of unique patterns encountered in a MD file are listed in a file, along with the following details.

\begin{itemize}
 \item The code iterators used in the machine. This is important, because the code iterators acts as aliases to operators and this alias is 
specific to a particular machine. So reading the patterns back won't make much sense without the code iterators listed.
\item The height of the pattern. The height here is height of the tree that represents this pattern.
\item The number of times this particular pattern is encountered in the files that are parsed.
\item The total number of RTL templates considered for parsing.
\end{itemize}


A function, AddToPatternList, is used to get the list of unique patterns found in the machine description files of a machine. This 
function(refer Algorithm\ref{AddToPatternList}) 
maintains a list of patterns, sorted in the increasing order of their heights. When a new pattern is encountered, it is compared with 
patterns of same height for equality and added to the list, if it is not already present. The patterns are sorted by their heights, so
that unwanted comparison between patterns of dissimilar heights are avoided.

\begin{algorithm}
\caption{AddToPatternList (p)}
 

\label{AddToPatternList}
\begin{algorithmic}

% \Procedure{AddToPatternList}{p}


\STATE $height := get\_height(p)$
% \COMMENT {hello.}


\IF {plist is empty }
	\STATE Add p to plist.  \COMMENT {plist, is a global variable and points to a list of patterns.}

\ELSE
	\STATE Skip over all patterns,pat, such that  $get\_height(pat) < height$. 

	\IF {There are patterns pat, such that $get\_height(pat) \geq height$}
		\WHILE { As long as plist has more patterns and current pattern, $pat\rightarrow height = height$}
				\STATE Compare the input pattern p and pat for equality.
			\IF { $p = pat$}
				\STATE Break out of loop.
			\ENDIF
		\ENDWHILE

		\IF {plist has more patterns}
      		{
       			\IF {$pat\rightarrow height = height$}
         	  	{
            			\STATE The input pattern, p, is already added to the list.So just increase the count for this pattern.
            
         		}
         		\ELSE
         		{
           	  		\STATE The input pattern p, is not in the list. Insert this pattern to the list.
                 	}
			\ENDIF
      		}
		
	
		\ELSE
		{
			\STATE None of the patterns in the list matches the input pattern and it is safe to add this pattern to the end of the list.
		}
		\ENDIF

	\ELSE
        { 
		\STATE All the patterns in the plist are of height less than the input pattern.
       	 	So insert this pattern to the end of the list.
        }  
	\ENDIF		


\ENDIF
\end{algorithmic}
\end{algorithm}

% \begin{verbatim}
% AddToPatternList 
% 
% Input : A pattern p
% 
% Output : None
% 
% Global variable : plist of type pattern_list (stands for pattern list, the list of 
%                   patterns)
% 
% 
%   height = get_height(p)
% 
%   if (NULL == plist)
%   {
%     plist = new_pattern_list(p)
%     plist->height = height
%     plist->count = 1;
%     plist->next = NULL
%   }
% 
%   else
%   {
%     pattern_list temp = plist
%     pattern_list prev = NULL
%     //skip over all patterns whose height is less than the input pattern's height
%     while (temp && (temp-> height < height))
%     {
%       prev = temp
%       temp = temp->next
%     }
% 
%     if (temp)
%     {
%       //implies there are patterns of height greater than or equal to the input pattern's 
%       //height
%       while (temp && (temp->height == height))
%       {
%          // as long as temp is not null and temp's height is equal to input 
%          //pattern's height compare the input pattern
%          // and temp's pattern for equality
%          if (TRUE == compare_patterns(temp->pattern, p))
%              break;
%          prev = temp
%          temp = temp->next
%       }
%       
%       if (temp)
%       {
%          if (temp->height == height)
%          {
%             //the input pattern is already added to the list.
%             //so just increase the count for this pattern
%             temp->count = temp->count + 1
%          }
%          else
%          {
%             // the input pattern is not in the list. insert this pattern
%             //between prev and temp
%             prev->next = new_pattern_list(p)
%             prev->next->height = height
%             prev->next->count = 1
%             prev->next->next = temp
%          }
%       }
%       else
%       {
%          //none of the patterns in the list matches the input pattern and 
%          //it is safe to add this pattern to the end of the list
%          prev->next = new_pattern_list(p)
%          prev->next->height = height
%          prev->next->count = 1
%          prev->next->next = temp
%       }
% 
% 
%     }
%     else
%     {
%       // all the patterns in the plist are of height less 
%       //than the input pattern.
%       // so insert this pattern to the end of the list.
%       prev->next = new_pattern_list(p)
%       prev->next->height = height
%       prev->next->count = 1
%       prev->next->next = NULL
% 
%     }
% 
% 
%   }
%  
% \end{verbatim}



The input to the above function is a pattern p. To get the pattern p, from an RTL Template of an instruction, say a define\_insn
expression, the RTL template is passed to a function extractPattern, which accepts an RTL template and returns the corresponding
pattern. The pattern thus returned is passed to the above function.


\section {Output Format}

After parsing the machine description files of a machine, the output is written on to a file. Initially, the code iterators found
in the machine are listed down. Then the patterns are listed one by one in the increasing order of their heights. Along with the
patterns, their height and the number of times that pattern occurs in the MD file are also listed.

\begin{verbatim}
Pattern_format : code_iterators patterns
               ;
code_iterators	: //Empty pattern
                |
                  code_iterators code_iterator
                ;
code_iterator   : [SNO] code_iterator_expression
                ;
patterns	://Empty Pattern 
                |
                  patterns pattern
                ;
pattern 	:[SNO][HEIGHT][COUNT] pattern_expression
                ;
\end{verbatim}


A grammar is written to read code\_iterator\_expression and also the pattern\_expression, so that they can be read back from 
file and represented as trees in memory for further use. 


For the addition instructions of the machine MIPS, the patterns extracted
and printed will look like this


\begin{verbatim}
[1][2][17] (set <<:m>> (<<re>>)(plus <<:m>> (<<re>>)(<<re>>)))
[2][3][2] (set <<:m>> (<<re>>)(sign_extend <<:m>> 
                               (plus <<:m>> (<<re>>)(<<re>>))))
[3][4][2] (set <<:m>> (<<re>>)(zero_extend <<:m>> 
                              (subreg <<:m>> 
                              (plus <<:m>> (<<re>>)(<<re>>))
                               <<offset>>)))
[4][4][1] (set <<:m>> (<<re>>)(zero_extend <<:m>> 
                               (truncate <<:m>> 
                               (plus <<:m>> (<<re>>)(<<re>>)))))
\end{verbatim}


The instructions defining addition operation don't use code iterators. So the code iterators are not listed above.
In the first line, the value {\tt [1]} represents the index, the value {\tt [2]} represents the height of the pattern and the value 
{\tt [17]} 
represents the number of times this pattern occurs in the input file that was parsed. Followed by this, the pattern is listed.
Any text within the two angle brackets represents machine specific values which are to be filled to get the RTL template. The textual 
form of the patterns is similar to the textual form of the 
RTL expressions found in machine description files. They are written in similar fashion, with the parentheses used in the same way as in a regular
RTL expression. In the textual form of RTL, any RTL expression is written within a pair of parenthesis. An RTL vector, which is a vector of RTL
expressions, is enclosed within a pair of square brackets.
The only difference in the pattern's representation is that any machine-specific value is removed, and is replaced by a meaningful text enclosed within 
two angled brackets. So anyone familiar 
with RTL expression's textual form can easily read and understand the pattern files.


\section {Finding Common Patterns between two machines}

One interesting application of the parsing discussed above is, given two machines, we can get an idea about the number
of patterns that are common between them. Note that, with each pattern p\textsubscript{i}, we associate a count. This count, tells us the 
number of actual templates that have this pattern as its form, or conversely, the number of templates that can be formed on this
machine by supplying machine-specific parameters to this pattern.

Given two files, each containing the pattern list of a machine, a list of common patterns is output into a file with the following details,

\begin{itemize}
 \item The list of code\_iterators common between the two machines.
 \item The list of patterns that are common between the two machines.
\end{itemize}
 
The above listing has the same syntax as the pattern list file discussed in the previous section. The count associate with each pattern in this case means 
the number of templates that are common in both the machines.


\section {Instantiating Patterns with Parameters}

This section describes how to instantiate a pattern with machine-specific parameters to generate a complete RTL
template. For this we need the list of patterns which was output from the \emph{parse} option or the \emph{intersect} option.
We refer to the pattern to be instantiated with a number which indicates the index at which the pattern is listed in the
pattern file. The first pattern listed gets the number 1, the second 2 and so on. To instantiate a pattern we use the notation,

\begin{verbatim}
 [$$INDEX ARGUMENTS]
\end{verbatim}

The INDEX above represents the index of the pattern in the pattern\_list. The ARGUMENTS, is list of machine-specific values that 
are to be used by the pattern indicated by index to complete the pattern to get the complete RTL Template. The arguments are
listed in an in-order fashion. The use of parenthesis and square brackets is similar to the RTL's textual representation. The arguments for an
RTL expression are listed within a pair of parenthesis, while that of an RTL vector are enclosed within square brackets.

Let us illustrate this with an example. The addition specific instructions from the MD file of the MIPS machine is parsed and we get the below list of patterns.


\begin{verbatim}
[1][2][17] (set <<:m>> (<<re>>)(plus <<:m>> (<<re>>)(<<re>>)))
[2][3][2] (set <<:m>> (<<re>>)(sign_extend <<:m>> 
                              (plus <<:m>> (<<re>>)(<<re>>))))
[3][4][2] (set <<:m>> (<<re>>)(zero_extend <<:m>> (subreg <<:m>> 
                              (plus <<:m>> (<<re>>)(<<re>>))<<offset>>)))
[4][4][1] (set <<:m>> (<<re>>)(zero_extend <<:m>> 
                              (truncate <<:m>> 
                               (plus <<:m>> (<<re>>)(<<re>>)))))
\end{verbatim}

To instantiate one of the patterns above, say pattern 3, with operands, we can use the below construct,

\begin{verbatim}
[$$3(null (match_operand:SI 0 "register_operand" "=d")
        (SI (QI
	    (SI (match_operand:SI 1 "register_operand" "d")
		 (match_operand:SI 2 "register_operand" "d")) 
	      3)))]
\end{verbatim}

In the above statement, \$\$3 corresponds to the pattern 3 in the pattern list, listed above.  On 
reading the pattern, a tree, say T1 as shown in Figure\ref{fig:FigureT1}, of the pattern is created internally. Followed
by this, the arguments to this pattern are listed. A grammar has been written to parse the arguments. This grammar reads the
arguments and creates a tree say T2 as shown in Figure\ref{fig:FigureT2}, for this argument. The next step will be to merge these two trees T1 and T2, the pattern and the 
argument to get the actual template with the complete machine-specific values as shown in Figure\ref{fig:MergedTree}.


\begin{figure}[h]
\centering%
\includegraphics[scale = 0.5]{G2.pdf}
\caption{Pattern-Tree T1}
\label{fig:FigureT1}
\end{figure}

\begin{figure}[h]
\centering%
\includegraphics[scale = 0.5]{T2.pdf}
\caption{Argument-Tree T2}
\label{fig:FigureT2}
\end{figure}

\begin{figure}[h]
\centering%
\includegraphics[scale = 0.5]{T3.pdf}
\caption{Merged Tree}
\label{fig:MergedTree}
\end{figure}



\section{Merging Pattern Files}

This section describes how a set union of patterns is performed given a list of files with pattern lists. Previously we saw that a grammar was written to read pattern files
using which common patterns between two machines were listed. The same grammar is used to find the union of  patterns given two pattern files. 
If we have the pattern-list files for
a set of architectures, with our capability to perform union and intersection operation on patterns, we can create a basis set of patterns that are common to a majority
of the architectures.

A naive approach for getting the minimal set is suggested below. 
Say, there are pattern-list files f1, f2, f3,..,fn for machines m1, m2, m3,...,mn. We can modify the count associated with each pattern as 1. Then we can perform an union of
all the pattern files and then output only those patterns which occurs in at least in a specific number(threshold), say half the number of machines. This threshold can be made
configurable by the user. With this in place, we can get the basis set of patterns needed to build new MD files.
 

\section{Separating Machine-specific parameters from Templates}
We developed a method to split an RTL template into patterns and parameters i.e., given
an RTL template in its input, it splits the RTL template into the index value of its corresponding pattern and the machine-specific
values as operands. The RTL templates in this format is written to an output file. 

Developing this method served two purposes. The first one was to test our strategy to instantiate RTL patterns with parameters as discussed in the previous section, 
using real MD files. 
The MD files of existing machines were first split into pattern-index and machine-specific operands using this method and written to an output file. Then we 
tested creating RTL templates back from the output file created in the previous step.

The second purpose was in removing redundancies in MD files. Later in the next chapter, we'll show 
through experimental results that, patterns are repeated across RTL templates even within MD files of a single machine. Since, patterns are extracted and listed only once,
this method helps removing redundancies.


\section{Summary}

In summary, we looked at what is a pattern of an RTL expression and how this could be separated from an RTL template. Then we saw how MD files were 
tested for similarities and how the patterns can be instantiated with machine-specific parameters to construct new RTL templates.




 
 